[BAEKJOON] 2092. 집합의 개수

문제 :

1부터 T(1 ≤ T ≤ 200)까지의 범위에 있는 수들이 총 A개 있다. 이들 중 K개를 골라서 집합을 만들 때, 가능한 집합의 개수를 세려 한다. 단, K의 범위는 1 ≤ S ≤ K ≤ B ≤ A로 한다. 즉, 두 정수 S, B를 입력받아서 K=S일 경우, …, K=B일 경우의 집합의 개수를 모두 더하려고 한다.

예를 들어 T=3, 수들이 1, 1, 2, 2, 3인 경우를 생각해 보면, 각기 다음의 경우가 있다.

• K=1 : {1}, {2}, {3}
• K=2 : {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}
• K=3 : {1, 1, 2} {1, 1, 3} {1, 2, 2} {1, 2, 3} {2, 2, 3}
• K=4 : {1, 2, 2, 3} {1, 1, 2, 2} {1, 1, 2, 3}
• K=5 : {1, 1, 2, 2, 3}

따라서 S=2, B=3일 경우의 답은 10이 된다.

우리가 일반적으로 이야기하는 집합은 같은 원소를 허용하지 않는다. 이 문제에서의 집합은 같은 원소가 없다는 사실 보다는, 집합의 각 원소들의 순서를 바꾸어도 같은 집합이라는 사실에 주목하여 풀도록 한다. 즉, {1, 1, 2}는 하나의 집합이고, {1, 2, 1}은 이와 같은 집합이다.

입력 :

첫째 줄에 네 정수 T, A, S, B가 주어진다. 다음 줄에는 A개의 수가 차례로 주어진다. (1 ≤ A ≤ 4000)

출력 :

첫째 줄에 답을 1,000,000으로 나눈 나머지를 출력한다.

풀이 :

문제 접근부터 쉽지 않아서 결국은 솔루션을 참고해서 푼 문제였다. 우선 DP를 사용해야 한다고 생각이 들고나서도 어떤 데이터를 메모이제이션해야할지 쉽게 감이 오지 않았다. 대표적인 유형들의 DP 문제들에서 벗어난 문제들을 풀어봄으로써 좀 더 유연하게 사고하는 연습이 필요한 듯 하다.

[세부 구현사항]

• 본 문제의 키포인트는 각 숫자들을 몇개씩 사용해서 만들었는지를 세는 조합 문제이라는 것이다. 그래서 나는 코드에서 cntary[] 배열을 사용하여 각 숫자들이 몇 개씩 있는지 카운트하였다.
• dp 메모이제이션 배열을 구성할 때의 키포인트는 바로 각 숫자들 하나만을 사용해서 만들 수 있는 조합 개수를 통해 누적합을 더해가는 방식을 사용해야 한다는 것이다. => 쉽게 말해서 한 숫자만을 사용해서 만들 수 있는 조합은 항상 그 숫자의 갯수(공집합 제외할 시)만큼 나타난다(ex. 5가 3개 있을 경우 {공집합}, {5}, {5, 5}, {5, 5, 5}) 이렇게 한 숫자만을 사용해서 만들 수 있는 조합을 그보다 작은 숫자들을 이용해 만들 수 있는 경우의 수를 누적합해주면 dp 메모이제이션을 해결할 수 있다.
• dp배열은 행 : 사용 숫자 범위, 열 : 집합 원소 갯수 k개 로 구성된다.
• dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % DVD => (조건, 0<k<=cntary[i])

처음에는 각 숫자들을 떼서 한 숫자로 만들 수 있는 조합을 붙여가며 메모이제이션할 생각을 전혀 하지 못했다. 당연히 조합 문제는 재귀 방식으로 탐색하면서 백트래킹을 활용해야할 것이라는 생각에서 벗어나지 못해 로직을 쉽게 떠올리지 못한 것 같다.

코드 :

#include <iostream>

#define DVD 1000000

using namespace std;
int dp[201][4001], cntary[201];

int main() {
    int range, n, start, end, input, answer = 0;
    cin >> range >> n >> start >> end;

    for (int i = 0; i < n; i++) {
        cin >> input;
        cntary[input]++;
    }

    for (int i = 0; i <= cntary[1]; i++)
        dp[1][i] = 1;

    for (int i = 2; i <= 200; i++) {
        dp[i][0] = 1;
        for (int j = 1; j <= n; j++) {
            int cntval = cntary[i];
            for (int k = 0; k <= cntval; k++)
                if (k <= j) dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % DVD;
        }
    }

    for (int k = start; k <= end; k++)
        answer = (answer + dp[200][k]) % DVD;

    cout << answer << '\n';
    return 0;
}